﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Expressions;
using System.Diagnostics.Contracts;

namespace FoundationLib.Common.Extensions
{
	/// <summary>
	/// Defines extension methods for enumerable types.
	/// </summary>
	public static class EnumerableExtensions
	{
		/// <summary>
		/// Performs a topological depth-first sort on the given source using the specified predecessor property expression.
		/// </summary>
		/// <remarks>
		/// This implementation uses recursion to perform a depth-first topological sort. It indirectly detects 
		/// circular dependencies between nodes by keeping track of visited nodes and breaks the 
		/// recursion sequence once a node has been visited twice. In that case the result is not guaranteed
		/// to contain all input nodes, nor are these nodes guaranteed to be in the correct topological order. 
		/// Therefore, callers should check the dimensions of source and result lists and make 
		/// sure both lists contain an equal number of nodes before using the result.
		/// </remarks>
		/// <typeparam name="T">The node type</typeparam>
		/// <param name="source">The data source</param>
		/// <param name="predecessors">A property expression pointing to the list of predecessor nodes</param>
		/// <returns>A sorted list</returns>
		public static IEnumerable<T> SortTopologically<T>(this IEnumerable<T> source, Expression<Func<T, IEnumerable<T>>> predecessors)
		{
			Contract.Requires(source != null);
			Contract.Requires(predecessors != null);
			Contract.Ensures(Contract.Result<IEnumerable<T>>() != null);
			
			List<T> result = new List<T>();
			List<T> visited = new List<T>();
			foreach (T item in source)
			{
				AddRecursively<T>(item, predecessors, result, visited);
			}

			return result;
		}

		/// <summary>
		/// Recursively adds nodes to the result list starting with the given node.
		/// </summary>
		/// <typeparam name="T">The type of node</typeparam>
		/// <param name="node">The start node</param>
		/// <param name="predecessors">A property expression pointing to the list of predecessor nodes</param>
		/// <param name="result">The result list</param>
		/// <param name="visited">The list of nodes already visited (used for detecting circular dependencies)</param>
		private static void AddRecursively<T>(T node, Expression<Func<T, IEnumerable<T>>> predecessors, List<T> result, 
			List<T> visited)
		{
			Contract.Requires(node != null);
			Contract.Requires(predecessors != null);
			Contract.Requires(result != null);
			Contract.Requires(visited != null);

			//Familiar face?
			if (!visited.Contains(node))
			{
				visited.Add(node);
				IEnumerable<T> dependencies = predecessors.Compile().Invoke(node);
				//Predecessors should at least contain an empty list, but better make sure that's really the case
				if (dependencies != null)
				{
					foreach (T item in dependencies)
						AddRecursively(item, predecessors, result, visited);
				}
				//All predecessors in the chain should be in the list, now it's safe to add this node.
				result.Add(node);
			}
			else
			{
				//Circular reference detected... that's no good, stop recursion to prevent infinite loop
				return;
			}
		}

	}
}
